#include <stdlib.h>
#include <stdio.h>
#include <unistd.h>
#include <pthread.h>
#include <semaphore.h>

#include "pool.h"

#define BLOCK_SIZE 100
#define BLOCK_NUM 80

typedef struct _free_block {
    int size;
    char * addr;
    struct _free_block * next;
}free_block;

typedef struct _busy_block {
    int size;
    pthread_t tid;
    char * addr;
    struct _busy_block * next;
}busy_block;

typedef struct {
    char * block;
    free_block * free_head;
    busy_block * busy_head;
}memory;

typedef struct _s{
    int No;
    char name[20];
    struct _s * next;
}student;

memory my_memory;
int init_memory(){
    my_memory.block = (char *)malloc(BLOCK_SIZE * BLOCK_NUM);
    my_memory.free_head = (free_block *)malloc(sizeof(free_block));
    my_memory.busy_head = (busy_block *)malloc(sizeof(busy_block));
    free_block * p = (free_block *)malloc(sizeof(free_block));
    p->addr = my_memory.block;
    p->size = BLOCK_SIZE * BLOCK_NUM;
    p->next = NULL;
    my_memory.free_head->size = -1;
    my_memory.free_head->next = p;
    my_memory.free_head->addr = NULL;

    my_memory.busy_head->size = -1;
    my_memory.busy_head->next = NULL;
    my_memory.busy_head->addr = NULL;
    my_memory.busy_head->tid = 0;

    return 0;
}

char * ff_alloc(int size){
    // printf("FF allocate.\n");
    char * addr = NULL;
    free_block *q, * p = my_memory.free_head;
    while(p->next){
        q = p;
        p = p->next;
        if(size <= p->size){
            p->size -= size;
            addr = p->addr;
            p->addr += size;
            if(!p->size){
                q->next = p->next;
                free(p);
            }
            busy_block * b =  (busy_block *)malloc(sizeof(busy_block));
            b->next = my_memory.busy_head->next;
            b->size = size;
            b->addr = addr;
            b->tid = pthread_self();
            my_memory.busy_head->next = b;
            break;
        }
    }
    return addr;
}

char * bf_alloc(int size){
    // printf("BF allocate.\n");
    char * addr = NULL;
    int s;
    free_block *target, *p, *t_pre;
    free_block *q = my_memory.free_head;
    target = q->next;
    while(q->next){
        p = q;
        q = q->next;
        if(q->size >= size){
            if(q->size <= target->size){
                t_pre = p;
                target = q;
                addr = target->addr;
            }
        }
    }
    if(target->size < size){
        printf("BF allocate error.\n");
        return NULL;
    }

    busy_block *  b = malloc(sizeof(busy_block));
    b->size = size;
    b->addr = target->addr;
    b->tid = pthread_self();
    b->next = my_memory.busy_head->next;
    my_memory.busy_head->next = b;

    target->size -= size;
    target->addr += size;
    if(target->size == 0){
        t_pre->next = target->next;
        free(target);
    }

    return addr;
}

char * wf_alloc(int size){
    // printf("WF allocate.\n");
    char * addr = NULL;
    free_block * p = my_memory.free_head;
    free_block * q, *target = p->next;
    q = p;
    while(p->next){
        if(p->next->size > target->size){
            q = p;
            target = p->next;
        }
        p = p->next;
    }

    if(target->size < size){
        printf("allocate error.\n");
        return NULL;
    }
    addr = target->addr;
    target->size -= size;
    target->addr += size;

    busy_block *  b = malloc(sizeof(busy_block));
    b->size = size;
    b->addr = target->addr;
    b->tid = pthread_self();
    b->next = my_memory.busy_head->next;
    my_memory.busy_head->next = b;

    if(!target->size){
        q->next = target->next;
        free(target);
    }

    return addr;
}

pthread_mutex_t mutex;
pthread_cond_t cond;
void * my_allocate(int size, int algorithm){
    static char *(*alloc[3])(int) = {ff_alloc, bf_alloc, wf_alloc};

    pthread_mutex_lock(&mutex);
    while(!my_memory.free_head->next){
        pthread_cond_wait(&cond, &mutex);
    }
    void *ptr = (void *)alloc[algorithm](size);
    pthread_mutex_unlock(&mutex);

    return ptr;
}

void sort_free_block(){
    free_block * p = my_memory.free_head;
    free_block *_q, * q = my_memory.free_head->next;
    p->next = NULL;
    while(q){
        _q = q->next;
        while(p->next){
            if(q->addr < p->next->addr){
                q->next = p->next;
                p->next = q;
                break;
            }
            p = p->next;
        }
        if(!p->next){
            q->next = p->next;
            p->next = q;
        }
        q = _q;
    }

    p = my_memory.free_head->next;
    while(p->next){
        q = p->next;
        if(!q) break;
        if(p->addr + p->size == q->addr){
            p->next = q->next;
            p->size += q->size;
            free(q);
        }
        p = p->next;
        if(!p) break;
    }

    return;
}

void my_free(void * ptr){
    pthread_mutex_lock(&mutex);
    int is_null = NULL == my_memory.free_head->next;
    char * addr = (char *)ptr;
    busy_block * p = my_memory.busy_head;
    busy_block * q;
    while(p->next){
        q = p;
        p = p->next;
        if(p->tid==pthread_self() && addr == p->addr){
            break;
        }
    }
    q->next = p->next;
    free_block * fr = (free_block *)malloc(sizeof(free_block));
    fr->addr = p->addr;
    fr->size = p->size;
    fr->next = my_memory.free_head->next;
    my_memory.free_head->next = fr;
    free(p);
    sort_free_block();
    if(is_null){
        pthread_cond_signal(&cond);
    }
    pthread_mutex_unlock(&mutex);
}

void LIFO_out(student * _node){
    student * node = _node;
    if(!node)return;
    LIFO_out(node->next);
    printf("NO.%d,\tName:%s\n", node->No, node->name);
    return;
}

void FIFO_out(student * _node){
    student * node = _node;
    while(node){
        printf("NO.%d,\tName:%s\n", node->No, node->name);
        node = node->next;
    }
    return;
}

void show(){
    pthread_mutex_lock(&mutex);
    free_block * fp = my_memory.free_head;
    int f_block_num = 0;
    int f_block_size_all = 0;
    while(fp->next){
        fp = fp->next;
        f_block_num++;
        f_block_size_all += fp->size;
    }

    busy_block * bp = my_memory.busy_head;
    int b_block_num = 0;
    int b_block_size_all = 0;
    while(bp->next){
        bp = bp->next;
        b_block_num++;
        b_block_size_all += bp->size;
    }
    pthread_mutex_unlock(&mutex);
    printf("内存区总大小\t\t 自由空间大小\t\t 已用空间大小 \n");
    printf("%-12d\t\t %-10d\t\t %-10d\n", f_block_size_all+b_block_size_all, f_block_size_all, b_block_size_all);
    printf("总份数  %-10d\t %-10d\t\t %-10d\n\n", f_block_num+b_block_num, f_block_num, b_block_num);
}

pthread_mutex_t io_mutex;
void * test_task(void * arg){
    int number = *(int *)arg;
    student * s = (student *)my_allocate(sizeof(student), 2);
    student * temp, *p = s;
    // printf("%u\n", pthread_self());
    for(int i = 0; i < number; i++){
        temp = (student *)my_allocate(sizeof(student), 2);
        temp->next = NULL;
        pthread_mutex_lock(&io_mutex);
        printf("\n学号：");
        scanf("%d", &temp->No);
        printf("\n姓名：");
        scanf("%s", temp->name);
        pthread_mutex_unlock(&io_mutex);
        p->next = temp;
        p=p->next;
    }
    pthread_mutex_lock(&io_mutex);
    printf("FIFO OUT : \n");
    FIFO_out(s->next);
    printf("\n");
    printf("LIFO OUT : \n");
    LIFO_out(s->next);
    printf("\n");
    show();
    pthread_mutex_unlock(&io_mutex);
    p = s;
    while(p->next){
        temp = p;
        p = p->next;
        my_free((void *)temp);
    }
    my_free((void *)p);
}

int main(){
    init_memory();
    tPool * pool;
    if(create_pool(&pool, 2)){
        printf("create_pool failed!\n");
        exit(1);
    }
    int d[2];
    d[0] = 3;
    d[1] = 4;
    int a = add_task(pool, test_task, (void*)&d[0]);
    int b = add_task(pool, test_task, (void*)&d[1]);

    // show my_memory usage
    show();

    sleep(3);

    destroy_pool(pool);

    return 0;
}